/*
*Universidad del Valle de Guatemala
* Roger Artemio Diaz Fuentes
* 12176
* Juan de Dios Chivalan Rojas
* 12175
* Esta es la implementacion del lugares.
* Descripcion: Aqui se implementa el algoritmos de Floyd 
* 
 */
package hojas9;

//se importan estas librerias
import java.io.IOException;
public class AlgoFloyd{
    
    int[][] nodos;
    int[] mayor;
    int central;
    int menor=10000;
    lugares departamentos= new lugares();
    MatrizGrafo matAdyacencia;
    
    
    //se contruye la clase y se lee datos de el archivo .txt
    public AlgoFloyd(){
        
        //progra defensiva
        try {
            departamentos.obtenerArchivo("datos.txt");
            departamentos.arregloNombres(); // Nombre de los nodos
            matAdyacencia = departamentos.matrizCostos(); // Peso de los arcos entre nodos
            nodos = new int[25][25]; // Matriz de nodos intermedios
            mayor = new int[25];
        } catch (IOException ex) {
            ex.printStackTrace();
        }
        for(int n=0;n<departamentos.grafoo.size();n++){
            for(int m=0;m<departamentos.grafoo.size();m++){
                nodos[n][m]=10000;
            }
        }
    }
    
     //algoritmo de Floyd para encontrar el camino mas corto entre todos los nodos
     
    public void caminoCorto(){
    //se hacen ciclos de verificar camino corto
        for(int k=0;k<matAdyacencia.size();k++){
            for(int i=0;i<matAdyacencia.size();i++){
                for(int j=0;j<matAdyacencia.size();j++){
                    if(matAdyacencia.getEdge(matAdyacencia.get(i),matAdyacencia.get(j))>(matAdyacencia.getEdge(matAdyacencia.get(i), matAdyacencia.get(k))+matAdyacencia.getEdge(matAdyacencia.get(k), matAdyacencia.get(j)))){
                        matAdyacencia.addEdge(matAdyacencia.get(i), matAdyacencia.get(j), (matAdyacencia.getEdge(matAdyacencia.get(i), matAdyacencia.get(k))+matAdyacencia.getEdge(matAdyacencia.get(k), matAdyacencia.get(j))));
                        nodos[i][j]=k;
                    }
                }
            }
        }
        
    }
    
    //busca y encuentra el centro del grafo
    public void centroGrafo(){
        caminoCorto();
        int n=0;       
        // Encontrar los maximos de cada columna de la matriz
        for(int i=0;i<matAdyacencia.size();i++){
            for(int j=0;j<matAdyacencia.size()-1;j++){
                int num1=matAdyacencia.getEdge(matAdyacencia.get(j), matAdyacencia.get(i));
                n=j;
                n++;
                int num2=matAdyacencia.getEdge(matAdyacencia.get(n), matAdyacencia.get(i));
                if(num1>num2){
                    mayor[i]=num1;
                }
                else{
                    mayor[i]=num2;
                }
            }
            n++;
        }
        // Encontrar el minimo de los maximos de cada columna
        for(int i=0;i<matAdyacencia.size();i++){
            int num1=mayor[i];
            if(num1<menor){
                central=i;
                menor=num1;
            }
        }
        //se imprime la respuesta del centro de grafo
        System.out.println("\nEl centro del grafo es: "+matAdyacencia.get(central)+"\n");
        
    }
}
